# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def mergeKLists(self, lists: list) -> ListNode:
        def merge(node1, node2):
            dummy = ListNode(None)
            cur = dummy
            while node1 and node2:
                val1 = node1.val
                val2 = node2.val
                if val1 <= val2:
                    cur.next = node1
                    node1 = node1.next
                else:
                    cur.next = node2
                    node2 = node2.next
                cur = cur.next
            while node1:
                cur.next = node1
                node1 = node1.next
                cur = cur.next
            while node2:
                cur.next = node2
                node2 = node2.next
                cur = cur.next

            return dummy.next

        def mergeList(array, start, end):
            if start == end:
                return array[start]
            if end - start == 1:
                return merge(array[start], array[end])
            mid = (end + start) // 2
            return merge(mergeList(array, start, mid),
                         mergeList(array, mid + 1, end))

        if len(lists) == 0:
            return None

        return mergeList(lists, 0, len(lists) - 1)
